Привет! Меня зовут Александр Курилкин, и я веду курс по алгоритмам в «ШАД Helper». В этом посте я разберу несколько задач из вступительных экзаменов прошлых лет, чтобы вы смогли увидеть, что вас ждет, и понять, чему мы сможем вас научить на нашем курсе. Надеюсь, что вы разделяете мою любовь к интересным задачам по алгоритмам и получите искреннее удовольствие от прочтения этого поста! Итак, приступим…
28.05.2016, №4
Даны отрезков . Назовем индексом вложенности отрезка количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложенности, превышающим 1000. Ограничение по времени — , по дополнительной памяти — .
Воспользуемся методом, который в среде олимпиадников называется "сканлайн". Его суть в том, что мы сводим задачу к набору каких-то событий, которые обрабатываем в отсортированном порядке, что-то при этом делая, таким образом решая задачу. В данном случае для каждого отрезка создадим события "отрез
